﻿#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>

template <typename T>
class BST {
private:
    // 二叉树节点结构
    struct Node {
        T data;         // 节点存储的数据
        Node* left;     // 左子节点指针
        Node* right;    // 右子节点指针

        Node(T value) : data(value), left(nullptr), right(nullptr) {}
    };
public:
    // 构造函数
    BST() : root(nullptr) {}

    Node* root;  // 根节点指针

    void insert(T value) {
		root = insert(root, value);
    } // 插入节点的辅助函数
      /*
    先创建根节点创建对象插入，在左边和右边节点插入，在插入时判断值小于节点值插入左边，大于节点值插入右边，等于不插入

    */
    Node* insert(Node* node, T value) {
        if (node == nullptr) {
            return new Node(value);
        }

        if (value < node->data) {
            node->left = insert(node->left, value);  // 插入到左子树
        }
        else if (value > node->data) {
            node->right = insert(node->right, value); // 插入到右子树
        }

        return node;
    
    }
    // 层次遍历（广度优先）
  /*  void levelOrder() const {
        if (root == nullptr) return;

        std::queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            Node* current = q.front();
            q.pop();
            std::cout << current->data << " ";

            if (current->left != nullptr) q.push(current->left);
            if (current->right != nullptr) q.push(current->right);
        }
        std::cout << std::endl;
    }*/

    void levelOrder() {
        if (root == nullptr) return;
        
		std::queue<Node*> q; // 创建一个队列用于存储节点
		q.push(root); // 将根节点入队
        while (!q.empty()) {
			Node* current = q.front(); // 获取队列前端的节点
			q.pop(); // 将前端节点出队
			std::cout << current->data << " "; // 输出当前节点的数据
			if (current->left != nullptr) q.push(current->left); // 如果左子节点不为空，将其入队
			if (current->right != nullptr) q.push(current->right); // 如果右子节点不为空，将其入队
        }
		std::cout << std::endl; // 输出换行符

    }
};

void main() {
    BST<int> tree;  // 创建一个存储整数的二叉搜索树
    tree.insert(5);// 插入节点
    tree.insert(51);// 插入节点
    tree.insert(52);// 插入节点
    tree.insert(3);// 插入节点
	tree.levelOrder(); // 层次遍历输出
	//tree.forntOrder(); // 层次遍历输出
    //tree.insert(3);
    //tree.insert(7);
    //tree.insert(2);
    //tree.insert(4);
    //std::cout << "In-order Traversal: ";
    //tree.inOrderTraversal(); // 中序遍历输出
    //std::cout << "Search for 4: " << (tree.search(4) ? "Found" : "Not Found") << std::endl;
    //std::cout << "Search for 6: " << (tree.search(6) ? "Found" : "Not Found") << std::endl;
    //tree.remove(3); // 删除节点
    //std::cout << "In-order Traversal after deleting 3: ";
    //tree.inOrderTraversal(); // 中序遍历输出
    return;
}